#ifndef _BTREE_H_
#define _BTREE_H_

#include <stdlib.h>

#define ORDER 10
#define MAX_TREE_LEVEL 20
#define WIDTH 100
#define MAX_KEY_VALUE 1000000

#define IS_NODE_FULL(btree, node) (node->entry_active == 2 * btree->order + 1)
#define IS_NODE_HALF_FULL(btree, node) (node->entry_active >= btree->order + 1)

// data entry
typedef struct {
	void * key;
	void * value;
} bt_entry;

// tree node structure
typedef struct bt_node {
	//struct bt_node * parent; // parent node
	//struct bt_node * pre;  // pre sibling node
	//struct bt_node * next; // next sibling node
	short entry_active;  // number of active entries
	short node_level;    // node level, the level of leaf nodes is 0
	bt_entry * entries[2 * ORDER + 1]; // entries in a node
	bt_node * children[2 * ORDER + 2]; // children pointers of a node
} bt_node;

// tree structure
typedef struct {
	short order;         // order of the tree
	struct bt_node * root;  // root of the tree
} bt_tree;


extern bt_tree * btree_create(short order);
extern void btree_search(bt_tree * btree, bt_entry * entry, bt_entry * search_result);
extern void btree_insert(bt_tree * btree, bt_entry * entry);
extern void btree_delete(bt_tree * btree, bt_entry * entry);
extern void btree_destroy(bt_tree * btree);

extern bt_node * allocate_btree_node(short order, short level);
extern short binary_search_euqal(bt_entry ** entries, short length, bt_entry * entry);
extern short binary_search_greater(bt_entry ** entries, short length, bt_entry * entry);
extern short linear_search_greater(bt_entry ** entries, short length, bt_entry * entry);

static short index_trace[MAX_TREE_LEVEL];
static bt_node * node_trace[MAX_TREE_LEVEL];
#endif 